package com.company.剑指offer每日刷题.普通版;

import java.util.HashSet;

/**
 * 剑指 Offer 52. 两个链表的第一个公共节点
 * 输入两个链表，找出它们的第一个公共节点。
 *
 * 示例 1：
 * 输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
 * 输出：Reference of the node with value = 8
 * 输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
 * */
public class GetIntersectionNode {
    public class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
            next = null;
        }
    }
    /**
     * 方法1.：散列表存储节点
     * 思路：先遍历 A 的所有节点，将其加入map中，然后遍历B所有的节点，去哈希表中找是否有相同的节点
     *
     * */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        HashSet<ListNode> set = new HashSet<>();
        while(headA != null){
            set.add(headA);
            headA = headA.next;
        }
        while(headB != null){
            if(!set.add(headB)){
                return headB;
            }
            headB = headB.next;
        }
        return null;
    }

    /**
     * 方法2.：双指针法
     * 思路：定义 node1,node2两个指针，分别指向A,B的头结点，
     *      1.node1遍历完A后，重新回到B的头节点；node2遍历完B后，重新回到A的头节点；
     *      2.当node1和node2所指同一个节点时候，这个节点就是A，B的相交节点。
     *      循环退出条件：
     *          1.node1 == node2 != null
     *          2.node1 == node2 == null
     * */

    public ListNode getIntersectionNode1(ListNode headA, ListNode headB) {
        ListNode node1 =  headA,node2 = headB;
        if(node1 == null || node2 == null) return null;
        while(node1 != node2){
            //退出条件：
            node1 = node1 != null? node1.next: headB;
            node2 = node2 != null ? node2.next: headA;
        /**
         * 错误写法：
         * node1 = node1.next != null? node1.next: headB;
         * node2 = node2.next != null ? node2.next: headA;
         * 原因：这样写的话，当A，B链表如果有相交节点是没问题的。但是如果不存在这个相交节点的时候，循环将无法退出，导致超时。
         * */
        }
        return node1;
    }
}
